/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/kth-smallest-number-in-sorted-matrix
   @Language: C++
   @Datetime: 16-02-09 05:56
   */
// Method 1, MinHeap, Time 390ms
class Solution {
	struct hashpair{
		size_t operator()(const pair<int,int> &p)const{
			return hash<int>()(p.first^p.second);
		}
	};

public:
	/**
	 * @param matrix: a matrix of integers
	 * @param k: an integer
	 * @return: the kth smallest number in the matrix
	 * Tip: From left top ([0,0] to right bottom), add each element
	 *      to Min Heap, and find heap top element's neighbour.
	 */
	int kthSmallest(vector<vector<int> > &mat, int k) {
		// write your code here
		if (mat.size()<1 || mat[0].size()<1) return 0;
		int row=mat.size(), col=mat[0].size(), i, j;

		typedef pair<int,pair<int,int> > Qode;  //val + <row,col>
		priority_queue<Qode,vector<Qode>,greater<Qode> > minqs;
		unordered_set<pair<int,int>,hashpair> vist;
		minqs.push(make_pair(mat[0][0],make_pair(0,0)));
		vist.insert(make_pair(0,0));

		while(k--){
			i=minqs.top().second.first, j=minqs.top().second.second;
			if (k==0) return minqs.top().first;
			minqs.pop();
			if (i+1<row && vist.find(make_pair(i+1,j))==vist.end()){
				minqs.push(make_pair(mat[i+1][j],make_pair(i+1,j)));
				vist.insert(make_pair(i+1,j));
			}
			if (j+1<col && vist.find(make_pair(i,j+1))==vist.end()){
				minqs.push(make_pair(mat[i][j+1],make_pair(i,j+1)));
				vist.insert(make_pair(i,j+1));
			}
		}
		return 0;
	}
};
